package com.wy.leetCode;

/**
 * @author HelloWorld
 * @create 2021/10/1 13:29
 * @email 154803771@qq.com
 */
public class KMP {
    public static void main(String[] args) {
        KMP kmp = new KMP();
        String haystack = "";
        String needle = "";
        System.out.println(kmp.strStr(haystack, needle));

    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }


    public int strStr(String haystack, String needle) {
        if (needle == ""){
            return 0;
        }
        int[] next = KMP.getNext(needle); // abaabcaba
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()){
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j == needle.length()){
            return i - j;
        }else return -1;
    }

    public static int[] getNext(String string){
        int i = 0, j = -1;
        int[] next = new int[string.length()];
        next[0] = -1;

        while (i < string.length() - 1){
            if (j == -1 || string.charAt(i) == string.charAt(j)){
                j++;
                i++;
                next[i] = j;
            }else {
                j = next[j];
            }
        }
        return next;
    }
}
